1. Field of the Invention
The present invention relates to an encoder, a decoder, and a coding system, and is particularly applicable to the Slepian-Wolf coding system used in, for example, distributed video coding.
2. Description of the Related Art
Distributed video coding (DVC) is a new coding method that has grown out of coding theoretical research by Slepian and Wolf and further work by Wyner, Ziv, and others. In one DVC method, the encoder carries out only intraframe coding, while the decoder carries out both intraframe and interframe decoding. Distributed video coding has been attracting considerable attention because it can greatly reduce the computational load on the encoder.
An example of distributed coding is outlined in FIG. 1, which is taken from Aaron et al., ‘Transform-Domain Wyner-Ziv Codec for Video’, Proc. SPIE Visual Communications and Image Processing, San Jose, Calif., 2004. In the encoder, a video image sequence is divided into key frames, to which conventional intraframe coding and decoding are applied, and so-called Wyner-Ziv frames, to which Slepian-Wolf coding and decoding processes are applied. In the encoding process, a discrete cosine transform (DCT) is used to transform each Wyner-Ziv frame to the coefficient domain, the coefficients are grouped into bands, the coefficients in the k-th band are quantized by a 2Mk-level quantizer, the quantized coefficients (qk) are expressed in fixed numbers of bits, and the bit planes are extracted and supplied to a Slepian-Wolf encoder that that produces information bits and error-correcting bits, called parity bits. The parity bits are stored in a buffer for transmission to the decoder. The information bits are discarded (as implied but not explicitly shown by Aaron et al.).
To decode a Wyner-Ziv frame, the decoder generates a predicted image by interpolation or extrapolation from one or more key frames, applies a DCT to convert the predicted image to the coefficient domain, groups the coefficients into bands, and inputs the coefficients in each band as side information to a Slepian-Wolf decoder (a type of turbo decoder) The Slepian-Wolf decoder requests the parity bits it needs to detect and correct errors in the side information. If necessary, further parity bits can be requested and the turbo decoding process can be repeated until a satisfactorily consistent result is obtained.
Finally, the decoded values and the side information are both used to reconstruct the coefficients of the Wyner-Ziv frame, and an inverse discrete cosine transform (IDCT) is carried out to recover the image.
FIG. 2 further illustrates the processes from Slepian-Wolf coding to Slepian-Wolf decoding. The systematic encoder 101 in the encoding apparatus 100A is a type of Slepian-Wolf turbo encoder that generates information bits and parity bits separately. The information bits are discarded; the parity bits are stored in a parity bit buffer 102. Some of the parity bits are sent immediately to a parity bit transmitter 203 and transmitted to the decoding apparatus 100B; the other parity bits are held until requested by the decoding apparatus 100B.
In the decoding apparatus 100B, the transmitted parity bits are received by a parity bit receiver 209 and placed in a parity bit buffer 108, from which they are supplied to an error correcting decoder 107. An information bit predictor 112 supplies predicted information bits to the error correcting decoder 107. The error correcting decoder 107 uses the parity bits to carry out an error-correcting decoding process. If this does not produce a satisfactory decoded result, a transmission request signal controller 213 generates a transmission request signal, which is transmitted by a transmission request signal transmitter 214 to the encoding apparatus 100A as a request for more parity bits. The request is received by a transmission request signal receiver 206 in the encoding apparatus 100A and passed to a parity bit transmission controller 205. Operating according to a predetermined table, the parity bit transmission controller 205 controls the parity bit buffer 102 and parity bit transmitter 203 so as to transfer additional parity bits from the parity bit buffer 102 to the parity bit transmitter 203 and transmit them to the decoding apparatus 100B. This process is iterated until a satisfactory decoded result is obtained.
The error correcting decoder 107 may use the maximum a-posteriori probability (MAP) decoding algorithm described by Sklar in Digital Communication: Fundamentals and Applications, Prentice-Hall, 2001. This algorithm, which is used in turbo coding and other coding methods, is a high-performance error-correcting decoding method in which the coder uses the parity bits and predicted information bits, which are predicted at the decoder, to calculate the probability that each information bit is 0 or 1.
The conventional coding and decoding operations are illustrated in FIGS. 3A, 3B, and 3C. The systematic encoder 101, represented schematically in FIG. 3A, is a convolutional encoder with a constraint length of three and a coding rate of one-half. At times n−1, n, and n+1, the encoder receives data bits d {1, 0, 0}, outputs them as information bits u {1, 0, 0}, and generates parity bits v {1, 0, 1}. The parity bit v (0) for time n, for example, is transmitted to the decoding apparatus 100B. The parity bits v (1) for times n−1 and n+1 are not transmitted (unless requested later), and the information bits u are never transmitted.
In the decoder, bit values are represented algebraically: a 0 parity bit is represented as −1, for example, and a 1 parity bit as +1. Predicted values x of information bits are represented by positive and negative values indicating likelihoods that the true value of the bit is 1 or 0. In FIG. 3B, the predicted values at time n are {1.5, 0.0, −0.6} and the received parity bit values y are {0.0, −1.0, 0.0}, where 0.0 represents a non-transmitted parity bit. The a-priori probabilities πi=0k are 0.5; a bit is equally likely to be 1 or 0 (π1=π0).
At an arbitrary time k, the encoder may be in one of four states (a, b, c, d) representing the two most recent input data bits. Branch metrics can be calculated for all possible state transitions from time k to time k+1. For example, a branch metric δi=0,m=1k for the transition from state a (m=a) caused by input of a data bit with value 0 (i=0) at time k at which the predicted value of the information bit xk, if consistent with the parity bit output at time k, is Akπi=0kexp(−xk/σ2), where Ak and σ2 are parameters. For the transition from state a at time n (k=n), when xk=0.0, to state a at time n+1, which is consistent with the output of the known parity bit value of 0 at time n, if the parameters Ak and σ2 are both equal to unity, the branch metric is calculated as follows.
                                                                        δ                k                                                      i                    =                    0                                    ,                                      m                    =                    a                                                              =                                                A                  k                                ⁢                                  π                  k                                      i                    =                    0                                                  ⁢                                  exp                  ⁡                                      (                                                                  -                                                  x                          k                                                                    /                                              σ                        2                                                              )                                                                                                                          =                              0.5                ⁢                                  exp                  ⁡                                      (                                          -                                              x                        k                                                              )                                                                                                                          =                              0.5                ⁢                                  exp                  ⁡                                      (                                          -                                              (                        0.0                        )                                                              )                                                                                                                          =              0.5                                                          (        1        )            
Branch metrics for the transitions from the other states b (10), c (01), and d (11) that produce 0 parity bits at time n are calculated similarly as shown by equations (2) to (4).
                                                                        δ                k                                                      i                    =                    0                                    ,                                      m                    =                    b                                                              =                                                A                  k                                ⁢                                  π                  k                                      i                    =                    0                                                  ⁢                                  exp                  ⁡                                      (                                                                  -                                                  x                          k                                                                    /                                              σ                        2                                                              )                                                                                                                          =                              0.5                ⁢                                  exp                  ⁡                                      (                                          -                                              x                        k                                                              )                                                                                                                          =                              0.5                ⁢                                  exp                  ⁡                                      (                                          -                                              (                        0.0                        )                                                              )                                                                                                                          =              0.5                                                          (        2        )                                                                                    δ                k                                                      i                    =                    1                                    ,                                      m                    =                    c                                                              =                                                A                  k                                ⁢                                  π                  k                                      i                    =                    0                                                  ⁢                                  exp                  ⁡                                      (                                                                  -                                                  x                          k                                                                    /                                              σ                        2                                                              )                                                                                                                          =                              0.5                ⁢                                  exp                  ⁡                                      (                                          -                                              x                        k                                                              )                                                                                                                          =                              0.5                ⁢                                  exp                  ⁡                                      (                                          -                                              (                        0.0                        )                                                              )                                                                                                                          =              0.5                                                          (        3        )                                                                                    δ                k                                                      i                    =                    1                                    ,                                      m                    =                    d                                                              =                                                A                  k                                ⁢                                  π                  k                                      i                    =                    0                                                  ⁢                                  exp                  ⁡                                      (                                                                  -                                                  x                          k                                                                    /                                              σ                        2                                                              )                                                                                                                          =                              0.5                ⁢                                  exp                  ⁡                                      (                                          -                                              x                        k                                                              )                                                                                                                          =                              0.5                ⁢                                  exp                  ⁡                                      (                                          -                                              (                        0.0                        )                                                              )                                                                                                                          =              0.5                                                          (        4        )            
If the parity bits are assumed to be received without corruption, there is zero likelihood that the parity bit value is 1, so the remaining branch metrics are zero as indicated in equations (5) to (8).δi=1,m=ak=0  (5)δi=1,m=bk=0  (6)δi=0,m=ck=0  (7)δi=0,m=dk=0  (8)
Given a guaranteed value of 0 for the parity bit input at the transition from time n to time n+1, in state a an information bit value of 1 cannot be output, as can be seen from the trellis diagram in FIG. 3C.
For the transition from time n−1 to time n, branch metrics are calculated as follows. If the state at time n−1 is a and if the encoding apparatus does not transmit a parity bit, the calculation can be divided into two cases, depending on whether the parity bit value is 0 or 1, and can be expressed by equations (9) and (10), in whichui=0k=n−1=1andui=1k=n−1=−1.Equation (9) gives the branch metric expressed by equation (11), and equation (10) gives the branch metric expressed by equation (12).
                                                                        δ                                  k                  =                                      n                    -                    1                                                                                        i                    =                    0                                    ,                  m                                            =                            ⁢                                                A                                      k                    =                                          n                      -                      1                                                                      ⁢                                  π                                      k                    =                                          n                      -                      1                                                                            i                    =                    0                                                  ⁢                                  exp                  ⁡                                      (                                                                  x                                                  k                          =                                                      n                            -                            1                                                                                              ⁢                                                                        u                                                      k                            =                                                          n                              -                              1                                                                                                            i                            =                            0                                                                          /                                                  σ                          2                                                                                      )                                                                                                                          =                            ⁢                                                A                                      k                    =                                          n                      -                      1                                                                      ⁢                                  π                                      k                    =                                          n                      -                      1                                                                            i                    =                    0                                                  ⁢                                  exp                  ⁡                                      (                                                                  -                                                  x                                                      k                            =                                                          n                              -                              1                                                                                                                          /                                              σ                        2                                                              )                                                                                                          (        9        )                                                                                    δ                                  k                  =                                      n                    -                    1                                                                                        i                    =                    1                                    ,                  m                                            =                            ⁢                                                A                                      k                    =                                          n                      -                      1                                                                      ⁢                                  π                                      k                    =                                          n                      -                      1                                                                            i                    =                    1                                                  ⁢                                  exp                  ⁡                                      (                                                                  x                                                  k                          =                                                      n                            -                            1                                                                                              ⁢                                                                        u                                                      k                            =                                                          n                              -                              1                                                                                                            i                            =                            1                                                                          /                                                  σ                          2                                                                                      )                                                                                                                          =                            ⁢                                                A                                      k                    =                                          n                      -                      1                                                                      ⁢                                  π                                      k                    =                                          n                      -                      1                                                                            i                    =                    1                                                  ⁢                                  exp                  ⁡                                      (                                                                  x                                                  k                          =                                                      n                            -                            1                                                                                              /                                              σ                        2                                                              )                                                                                                          (        10        )                                                                                    δ                                  k                  =                                      n                    -                    1                                                                                        i                    =                    1                                    ,                  m                                            =                            ⁢                                                A                                      k                    =                                          n                      -                      1                                                                      ⁢                                  π                                      k                    =                                          n                      -                      1                                                                            i                    =                    0                                                  ⁢                                  exp                  ⁡                                      (                                                                  -                                                  x                                                      k                            =                                                          n                              -                              1                                                                                                                          /                                              σ                        2                                                              )                                                                                                                          =                            ⁢                              0.5                ⁢                                  exp                  ⁡                                      (                                          -                                              x                                                  k                          =                                                      n                            -                            1                                                                                                                )                                                                                                                          =                            ⁢                              0.5                ⁢                                  exp                  ⁡                                      (                                          -                                              (                        1.5                        )                                                              )                                                                                                                          =                            ⁢              0.11                                                          (        11        )                                                                                    δ                                  k                  =                                      n                    -                    1                                                                                        i                    =                    1                                    ,                  m                                            =                            ⁢                                                A                                      k                    =                                          n                      -                      1                                                                      ⁢                                  π                                      k                    =                                          n                      -                      1                                                                            i                    =                    1                                                  ⁢                                  exp                  ⁡                                      (                                                                  x                                                  k                          =                                                      n                            -                            1                                                                                              /                                              σ                        2                                                              )                                                                                                                          =                            ⁢                              0.5                ⁢                                  exp                  ⁡                                      (                                          x                                              k                        =                                                  n                          -                          1                                                                                      )                                                                                                                          =                            ⁢                              0.5                ⁢                                  exp                  ⁡                                      (                    1.5                    )                                                                                                                          =                            ⁢              2.24                                                          (        12        )            
Branch metric calculations for the transition from time n+1 to time n+2 are the same as for the transition from time n to time n+1. The results are shown in FIG. 3C.
The method of calculating decoded bit values will be described with further reference to FIG. 3C.
A forward state metric α and backward state metric β for each state at each time can be calculated by multiplying the branch metrics of the paths converging on the state by the state metrics of the states from which those paths originate and adding the results. Given the state metrics at time n shown in FIG. 3C, for example, the forward state metric α for state a at time n+1 is calculated as in equation (13). The forward state metrics α for the other states are calculated similarly.α=0.14×0.50+0.56×0.0=0.07  (13)
The backward state metrics β are calculated in the same way as the forward state metrics α, except for the direction of calculation (right to left in FIG. 3C, instead of left to right).
The process for calculating decoded values will now be described. Specifically, the process of decoding the information bit for the transition from time n−1 to time n will be described. If an information bit value of 0 is assumed to have been input for the transition from time n−1 to time n, a value is calculated as expressed by equation (14). If an information bit value of 1 is assumed to have been input for the transition from time n−1 to time n, a value is calculated as expressed by equation (15). Based on these calculated values, the log likelihood of the bit value obtained by equation (16) is 1.31. As this value is positive, a decoded information bit value of 1 is obtained; the bit is correctly decoded.
                                                        α                              k                =                                  n                  -                  1                                                            m                =                a                                      ×                          δ                              k                =                                  n                  -                  1                                                                              i                  =                  0                                ,                                  m                  =                  a                                                      ×                          β                              k                =                n                                            m                =                a                                              +                                    α                              k                =                                  n                  -                  1                                                            m                =                b                                      ×                          δ                              k                =                                  n                  -                  1                                                                              i                  =                  0                                ,                                  m                  =                  b                                                      ×                          β                              k                =                n                                            m                =                c                                              +                                    α                              k                =                                  n                  -                  1                                                            m                =                c                                      ×                          δ                              k                =                                  n                  -                  1                                                                              i                  =                  0                                ,                                  m                  =                  c                                                      ×                          β                              k                =                n                                            m                =                a                                              +                                    α                              k                =                                  n                  -                  1                                                            m                =                d                                      ×                          δ                              k                =                                  n                  -                  1                                                                              i                  =                  0                                ,                                  m                  =                  d                                                      ×                          β                              k                =                n                                            m                =                c                                                    =                                            0.01              ×              0.11              ×              2.46                        +                          0.05              ×              0.11              ×              0.56                        +                          1.25              ×              0.11              ×              2.46                        +                          5.0              ×              0.11              ×              0.50                                =          0.620630285                                    (        14        )                                                                    α                              k                =                                  n                  -                  1                                                            m                =                a                                      ×                          δ                              k                =                                  n                  -                  1                                                                              i                  =                  1                                ,                                  m                  =                  a                                                      ×                          β                              k                =                n                                            m                =                b                                              +                                    α                              k                =                                  n                  -                  1                                                            m                =                b                                      ×                          δ                              k                =                                  n                  -                  1                                                                              i                  =                  1                                ,                                  m                  =                  b                                                      ×                          β                              k                =                n                                            m                =                d                                              +                                    α                              k                =                                  n                  -                  1                                                            m                =                c                                      ×                          δ                              k                =                                  n                  -                  1                                                                              i                  =                  1                                ,                                  m                  =                  c                                                      ×                          β                              k                =                n                                            m                =                b                                              +                                    α                              k                =                                  n                  -                  1                                                            m                =                d                                      ×                          δ                              k                =                                  n                  -                  1                                                                              i                  =                  1                                ,                                  m                  =                  d                                                      ×                          β                              k                =                n                                            m                =                d                                                    =                                            5.77              ×              2.24              ×              2.46                        +                          0.05              ×              2.24              ×              0.50                        +                          1.25              ×              2.24              ×              2.46                        +                          5.0              ×              2.24              ×              0.50                                =          12.63828944                                    (        15        )                                                          ⁢                              log            ⁢                                                  ⁢                          (                              12.63829                /                0.620630285                            ⁢                                                          )                                =          1.31                                    (        16        )            
The method of decoding an information bit for the transition from time n to time n+1 will now be described. If an information bit value of 0 is assumed to have been input for the transition from time n to time n+1, a value is calculated as expressed by equation (17). If an information bit value of 1 is assumed to have been input for the transition from time n to time n+1, a value is calculated as expressed by equation (18). Based on these calculated values, the log likelihood of the bit value obtained by equation (19) is −0.08. As this value is negative, a decoded information bit value of 0 is obtained; this bit is also decoded correctly.
                                                        α                              k                =                n                                            m                =                a                                      ×                          δ                              k                =                n                                                              i                  =                  0                                ,                                  m                  =                  a                                                      ×                          β                              k                =                                  n                  +                  1                                                            m                =                a                                              +                                    α                              k                =                n                                            m                =                b                                      ×                          δ                              k                =                n                                                              i                  =                  0                                ,                                  m                  =                  b                                                      ×                          β                              k                =                                  n                  +                  1                                                            m                =                c                                              +                                    α                              k                =                n                                            m                =                c                                      ×                          δ                              k                =                n                                                              i                  =                  0                                ,                                  m                  =                  c                                                      ×                          β                              k                =                                  n                  +                  1                                                            m                =                a                                              +                                    α                              k                =                n                                            m                =                d                                      ×                          δ                              k                =                n                                                              i                  =                  0                                ,                                  m                  =                  d                                                      ×                          β                              k                =                                  n                  +                  1                                                            m                =                c                                                    =                                            0.14              ×              0.50              ×              4.91                        +                          2.82              ×              0.50              ×              4.91                        +                          0.56              ×              0.0              ×              4.91                        +                          11.31              ×              0.0              ×              4.91                                =          7.27473285                                    (        17        )                                                                    α                              k                =                n                                            m                =                a                                      ×                          δ                              k                =                n                                                              i                  =                  1                                ,                                  m                  =                  a                                                      ×                          β                              k                =                                  n                  +                  1                                                            m                =                b                                              +                                    α                              k                =                n                                            m                =                b                                      ×                          δ                              k                =                n                                                              i                  =                  1                                ,                                  m                  =                  b                                                      ×                          β                              k                =                                  n                  +                  1                                                            m                =                d                                              +                                    α                              k                =                n                                            m                =                c                                      ×                          δ                              k                =                n                                                              i                  =                  1                                ,                                  m                  =                  c                                                      ×                          β                              k                =                                  n                  +                  1                                                            m                =                b                                              +                                    α                              k                =                n                                            m                =                d                                      ×                          δ                              k                =                n                                                              i                  =                  1                                ,                                  m                  =                  d                                                      ×                          β                              k                =                                  n                  +                  1                                                            m                =                d                                                    =                                            0.14              ×              0.0              ×              1.01                        +                          2.82              ×              0.0              ×              1.01                        +                          0.56              ×              0.50              ×              1.01                        +                          11.31              ×              0.50              ×              1.01                                =          5.984186875                                    (        18        )                                                          ⁢                              log            ⁢                                                  ⁢                          (                              5.984187                /                7.27473285                            ⁢                                                          )                                =                      -            0.08                                              (        19        )            
The method of decoding an information bit for the transition from time n+1 to time n+2 will also be described. If an information bit value of 0 is assumed to have been input for the transition from time n+1 to time n+2, a value is calculated as expressed by equation (20). If an information bit value of 1 is assumed to have been input for the transition from time n+1 to time n+2, a value is calculated as expressed by equation (21). Based on these calculated values, the log likelihood of the bit value obtained by equation (22) is −0.36. As this value is negative, a decoded information bit value of 0 is obtained, which is again the correctly decoded value of the bit.
                                                        α                              k                =                                  n                  +                  1                                                            m                =                a                                      ×                          δ                              k                =                                  n                  +                  1                                                                              i                  =                  0                                ,                                  m                  =                  a                                                      ×                          β                              k                =                                  n                  +                  2                                                            m                =                a                                              +                                    α                              k                =                                  n                  +                  1                                                            m                =                b                                      ×                          δ                              k                =                                  n                  +                  1                                                                              i                  =                  0                                ,                                  m                  =                  b                                                      ×                          β                              k                =                                  n                  +                  2                                                            m                =                c                                              +                                    α                              k                =                                  n                  +                  1                                                            m                =                c                                      ×                          δ                              k                =                                  n                  +                  1                                                                              i                  =                  0                                ,                                  m                  =                  c                                                      ×                          β                              k                =                                  n                  +                  2                                                            m                =                a                                              +                                    α                              k                =                                  n                  +                  1                                                            m                =                d                                      ×                          δ                              k                =                                  n                  +                  1                                                                              i                  =                  0                                ,                                  m                  =                  d                                                      ×                          β                              k                =                                  n                  +                  2                                                            m                =                c                                                    =                                            0.07              ×              0.91              ×              3.75                        +                          0.28              ×              0.91              ×              0.77                        +                          1.41              ×              0.91              ×              3.75                        +                          5.66              ×              0.91              ×              0.77                                =          9.209984875                                    (        20        )                                                                    α                              k                =                                  n                  +                  1                                                            m                =                a                                      ×                          δ                              k                =                                  n                  +                  1                                                                              i                  =                  1                                ,                                  m                  =                  a                                                      ×                          β                              k                =                                  n                  +                  2                                                            m                =                b                                              +                                    α                              k                =                                  n                  +                  1                                                            m                =                b                                      ×                          δ                              k                =                                  n                  +                  1                                                                              i                  =                  1                                ,                                  m                  =                  b                                                      ×                          β                              k                =                                  n                  +                  2                                                            m                =                d                                              +                                    α                              k                =                                  n                  +                  1                                                            m                =                c                                      ×                          δ                              k                =                                  n                  +                  1                                                                              i                  =                  1                                ,                                  m                  =                  c                                                      ×                          β                              k                =                                  n                  +                  2                                                            m                =                b                                              +                                    α                              k                =                                  n                  +                  1                                                            m                =                d                                      ×                          δ                              k                =                                  n                  +                  1                                                                              i                  =                  1                                ,                                  m                  =                  d                                                      ×                          β                              k                =                                  n                  +                  2                                                            m                =                d                                                    =                                            0.07              ×              0.27              ×              5.56                        +                          0.28              ×              0.27              ×              1.60                        +                          1.41              ×              0.27              ×              1.14                        +                          5.66              ×              0.27              ×              1.14                                =          4.04893485                                    (        21        )                                                          ⁢                              log            ⁢                                                  ⁢                          (                              4.048935                /                9.209984875                            ⁢                                                          )                                =                      -            0.36                                              (        22        )            
FIG. 4 illustrates the result of removing paths with branch metric values of zero from the trellis diagram in FIG. 3C. If a single parity bit can be received correctly, the computations for four paths can be eliminated, as shown in the figure.
The MAP algorithm is known to yield extremely good error-correcting results, but as these examples show, it requires extensive computation.
The algorithm allows high-speed processing of a relatively small amount of information, such as sound information, but high-speed processing of larger amounts of information, such as video image information, is difficult. A high-performance computing device (a high-performance microprocessor or central processing unit, for example) is required and much power is consumed.
The MAP algorithm also requires considerable memory space for storing computation results. This requirement, like the requirement for computing power, increases with the amount of information to be processed, so that more memory space is required for video and other massive types of information than for sound information. This requirement increases the size of the decoding apparatus.
There is a need for an encoder, a decoder, and a coding system that can reduce the necessary amounts of computation and memory in the decoder.